package DFS;

/**
 * @Author Fizz Pu
 * @Date 2021/5/12 下午7:32
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */



/**
 *
 */


public class LeeOffer108 {

    TreeNode root = null;

    public TreeNode sortedArrayToBST(int[] nums) {

        if(nums == null){
            return null;
        }

        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int start, int end){

        if(start > end){
            return null;
        }

        // int mid = (start + end) / 2;

        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        TreeNode node1 = buildBST(nums, start, mid - 1);
        TreeNode node2 = buildBST(nums, mid + 1, end);

        root.left = node1;
        root.right = node2;
        /*if(node1 != null && node2 == null){
            if(node1.val < root.val){
                root.left = node1;
            } else {
                root.right = node1;
            }
        }

        if(node1 == null && node2 != null){
            if(node2.val < root.val){
                root.left = node2;
            } else {
                root.right = node2;
            }
        }

        if(node1 != null && node2 != null){
            if(node1.val < root.val && node2.val > root.val){
                root.left = node1;
                root.right = node2;
            } else {
                root.left = node2;
                root.right = node1;
            }
        }*/
        return root;
    }
}
